package cn.edu.besti.cs2023.W2321;

public class BST_Maru {
    public BSTNode_Maru root;
    public BST_Maru(){
        this.root=null;
    }
    public void insertBST(int data){
        if (root==null){
            root=new BSTNode_Maru();
            root.key=data;
        }
        else {
            insertbst(this.root,data);
        }
    }
    public void insertbst(BSTNode_Maru node,int key){
        if(node==null||node.key==key){
            return;
        }else if (node.key>key){
            if (node.leftChild==null){
                BSTNode_Maru temp = new BSTNode_Maru();
                temp.key = key;
                node.leftChild = temp;
               // node.leftChild.key=key;
            }else {
                insertbst(node.leftChild,key);
            }

        }else {
            if (node.rightChild==null){
                BSTNode_Maru temp = new BSTNode_Maru();
                temp.key = key;
                node.rightChild = temp;
                // node.rightChild.key=key;
            }else{
                insertbst(node.rightChild,key);
            }
        }
    }
    public BSTNode_Maru BSTSearch(int key){
        if (this.root==null){
            return null;
        }else {
            if (this.root.key==key){
                return root;
            }
            else {
                return this.bstSearch(root,key);
            }
        }

    }
    public BSTNode_Maru bstSearch(BSTNode_Maru node,int key){
        if (node.key==key){
            return  node;
        }
        else if (node.key>key){
            if (node.leftChild!=null){
                return bstSearch(node.leftChild,key);
            }else {
                return null;
            }
        }else {
            if (node.rightChild!=null){
                return bstSearch(node.rightChild,key);
            }else {
                return null;
            }
        }
    }
    public boolean isBSTfound(int[] data,int target){
        BSTNode_Maru node=new BSTNode_Maru();
        BST_Maru Data=new BST_Maru();
        int temp;
        for (int i=0;i<data.length;i++){
            temp=data[i];
            Data.insertBST(temp);
        }
        node= Data.BSTSearch(target);
        if(node!=null)
            return true;
        return false;
    }

 class BSTNode_Maru {
    public int key;
    public BSTNode_Maru leftChild;
    public BSTNode_Maru rightChild;
    public BSTNode_Maru(){
        this.leftChild=null;
        this.rightChild=null;
    }
}
}

